package a09_贪心算法;


/**
 * <p>
 * a23_监控二叉树
 * </p>
 *
 * @author flyduck
 * @since 2025/1/17
 */
public class a23_监控二叉树 {
    //对于叶子节点，我们尽量在叶子节点的父节点放置摄像头
    //从下往上：后序遍历

    //节点状态：0无覆盖、1有摄像头、2覆盖

    //对空节点应该赋予什么状态才能统一规则到达最少摄像头的目的=》叶子节点的父节点放置摄像头
    //假设null节点是有摄像头的状态，那么叶子节点就是被覆盖的状态。那么叶子节点的父节点就不要放置摄像头了，违背了初衷
    //假设null节点是无覆盖的状态，那么叶子节点需要放置摄像头了，违背了初衷
    //假设null节点是覆盖的状态，那么叶子节点的父节点才需要放置摄像头√√√√√√

    //从下往上的时候如何做状态转移的
    //1、左右孩子都有覆盖=》父节点无覆盖(等着父节点的父节点装摄像头)
    //2、左右孩子至少一个无覆盖 => 父节点装摄像头
    //3、左右孩子至少一个有摄像头 => 父节点覆盖

    public static void main(String[] args) {
//        TreeNode treeNode = new TreeNode(0,
//                new TreeNode(0,
//                        new TreeNode(0),
//                        new TreeNode(0)),
//                null);
        TreeNode treeNode = new TreeNode(0);
        a23_监控二叉树 test = new a23_监控二叉树();
        int i = test.minCameraCover(treeNode);
        System.out.println(i);
    }

    public int minCameraCover(TreeNode root) {
        int result = traversal(root);
        if (result == 0) {//如果跟节点无覆盖，给跟节点装摄像头
            num++;
        }
        return num;
    }

    private int num;

    private int traversal(TreeNode node){
        if (node == null) {
            return 2;
        }
        int leftVal = traversal(node.left);
        int rightVal = traversal(node.right);
        if(leftVal == 2 && rightVal == 2){
            return 0;
        }else if(leftVal == 0 || rightVal == 0){
            num++;
            return 1;
        }else{
            return 2;
        }
    }


}
